package com.jinan.algorithm.dynamicProgramming;

import com.jinan.common.TreeNode;

public class Rob {
//    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
//    如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
//给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
    public static void main(String[] args) {
        System.out.println(rob1(new int[]{1,2,3,1}));
        System.out.println(Math.max(rob2(new int[]{1,2,3,1},0,2), rob2(new int[]{1,2,3,1},1,3)));

        TreeNode<Integer> node5 = new TreeNode<>(1,null,null);
        TreeNode<Integer> node4 = new TreeNode<>(3,null,null);
        TreeNode<Integer> node3 = new TreeNode<>(3,null,node5);
        TreeNode<Integer> node2 = new TreeNode<>(2,null,node4);
        TreeNode<Integer> node1 = new TreeNode<>(3,node2,node3);
        System.out.println(Math.max(rob3(node1)[0], rob3(node1)[1]));
    }

    /**
     * 198. 打家劫舍 <a href="https://leetcode-cn.com/problems/house-robber/">...</a>
     * 难度： 简单
     * tag: 动态规划
     * description:
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
     * restriction:
     * 1 <= nums.length <= 1000
     * 0 <= nums[i] <= 400
     * @param nums 房屋存放金额的非负整数数组
     * @return int 偷窃到的最高金额
     */
    public static int rob1(int[] nums) {
        if (nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }

//    首尾相连
    public static int rob2(int[] nums,int start,int end) {
        if (nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start], nums[start+1]);
        for (int i=start+2;i<=end;i++){
            dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[end];
    }
//    树形结构
//    树形DP问题。在这种情况下，每个节点代表一个房屋，左子节点和右子节点分别代表该房屋的相邻房屋。目标仍然是最大化偷窃的总金额，但不能偷窃相邻的房屋
/*
解决这种类型的问题，我们可以采用后序遍历二叉树和深度优先的方法，从叶子节点开始，递归地向上合并结果，最终得到根节点的结果即为所求。
具体算法如下：
对于每个节点，我们需要计算两种情况下的最大收益：
不偷窃当前节点（即偷窃它的子节点），此时收益为左右子节点的最大收益之和。
偷窃当前节点，此时收益为当前节点的价值加上其所有孙子节点的最大收益。
在递归过程中，我们只返回第一种情况的收益（不偷窃当前节点），因为我们不能同时偷窃相邻的节点（即当前节点和其直接子节点）。
最终，对于根节点，我们同样计算上述两种情况，并返回其中的最大值作为最终结果。
 */
    public static int[] rob3(TreeNode<Integer> treeNode) {
        if (treeNode == null){
            return new int[]{0,0};
        }
        int[] left=rob3(treeNode.left);
        int[] right=rob3(treeNode.right);
        int select= treeNode.val+left[0]+right[0];
        int notSelect=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{notSelect,select};
    }
}
